package try01;

public class SearchA2DMatrix {
	public void tester() {
		int[][] a = {{-8,-7,-5,-3,-3,-1,1},{2,2,2,3,3,5,7},{8,9,11,11,13,15,17},{18,18,18,20,20,20,21},{23,24,26,26,26,27,27},{28,29,29,30,32,32,34}};
		System.out.println(1+" "+searchMatrix(a, -5));
//		int t = (int)(10 * Math.random());
//		for(int i = 0 ; i < 5 ; i++) {
//			for(int j = 0 ; j < 5 ; j++) {
//				a}i][j] = t;
//				t = t + (int)(10 * Math.random());
//			}
//		}
//		for(int i = 0 ; i < 5 ; i++) {
//			for(int j = 0 ; j < 5 ; j++) {
//				
//			}
//		}
	}
	
	public boolean searchMatrix(int[][] matrix, int target) {
        int a = 0, b = matrix.length - 1;
        int mid = 0;
        
        while(a <= b) {
            mid = (a+b)/2;
            System.out.println("mid1: "+mid);
            if(matrix[mid][0] == target) return true;
            if(matrix[mid][0] > target) {
            	b = mid-1;
            }
            else { // matrix[mid][0] < target
            	if(mid < matrix.length-1 && matrix[mid+1][0] <= target) {
            		a = mid+1;
            	}
            	else {
            		break;
            	}
            }
        }
        
        int index = mid;
        System.out.println(index);
        
        a = 0;
        b = matrix[index].length - 1;
        
        while(a <= b) {
        	mid = (a+b)/2;
//        	System.out.println("mid2: "+mid);
            if(matrix[index][mid] == target) return true;
            if(matrix[index][mid] > target) b = mid-1;
            else a = mid+1;
        }
        
        return false;
    }
}
